import random

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def partitionLess(value, begin, end):
            a,b = begin,end
            while a<=b:
                while a<=b and nums[b]>=value: b-=1
                while a<=b and nums[a]<value: a+=1
                if a<b: nums[a], nums[b] = nums[b], nums[a]
            return min(a, end)
        def partitionGreater(value, begin, end):
            a,b = begin,end
            while a<=b:
                while a<=b and nums[b]<=value: b-=1
                while a<=b and nums[a]>value: a+=1
                if a<b:nums[a], nums[b] = nums[b], nums[a]
            return min(a, end)
        begin, end = 0, len(nums)-1
        while True:
            value = nums[random.randint(begin, end)]
            pivot = partitionLess(value, begin, end)
            if (pivot-begin)%2==1:
                end=pivot-1
                continue
            pivot = partitionGreater(value, begin, end)
            if (pivot-begin)%2==1:
                end=pivot-1
                continue
            return value
        assert(False)

print(Solution().singleNumber([17,12,5,-6,12,4,17,-5,2,-3,2,4,5,16,-3,-4,15,15,-4,-5,-6]))

                
